package array;

import java.util.Arrays;

/**
 * 给一个数组每一项加一直值，让其平均值接近某一个给定的值
 *
 * @author Liaorun
 */
public class ImageArrayAverageGotoHalf {

    public static void main(String[] args) {
        int zuo = zuo(new int[]{1, 2, 3}, 3);

        int best3 = best3(new int[]{1, 2, 3}, 3);
        System.out.println(zuo);
        System.out.println(best3);
    }


    public static int zuo(int[] arr, int s) {

        int l = -s;
        int r = s;
        int half = s / 2;

        int abs = Integer.MAX_VALUE;
        int ans = Integer.MAX_VALUE;

        while (l <= r) {
            int k = (l + r) / 2;
            int avg = avg(arr, s, k);

            // 差值更小 || (差值相等 && 当前加的值更小)
            if (Math.abs(avg - half) < abs || ((Math.abs(avg - half) == abs) && k < ans)) {
                // 更新差值和答案
                abs = avg - half;
                ans = k;
            }

            if (avg >= half) {
                // 当前的k值加的太大，左侧去二分
                r = k - 1;
            } else {
                // 当前的k值加的太小，右侧去二分
                l = k + 1;
            }
        }

        return ans;
    }

    /**
     * @param arr int 数组
     * @param s   加上k 之后不能大于 s, 如果大于就赋值为 s
     * @param k   给数组每个值 + 这个 k
     * @return 返回 arr 最后的平均值
     */
    public static int avg(int[] arr, int s, int k) {
        int sum = 0;

        for (int num : arr) {
            int v = num + k;

            if (v <= 0) {
                sum += 0;
            } else {
                sum += Math.min(v, s);
            }
        }
        return sum / arr.length;
    }


    /**
     * 正式方法，最优解
     * 时间复杂度：O(N * logN) + O(logS * logN)
     *
     * @param arr
     * @param s
     * @return
     */
    public static int best3(int[] arr, int s) {

        Arrays.sort(arr);

        // 计算当前数组的前缀和开始
        int[] sum = new int[arr.length];

        sum[0] = arr[0];

        for (int i = 1; i < arr.length; i++) {
            sum[i] = sum[i - 1] + arr[i];
        }
        // 计算当前数组的前缀和结束

        int l = -s;
        int r = s;
        int m = 0;
        int half = s / 2;
        int average = -s;
        int ans = 0;

        while (l <= r) {
            m = (l + r) / 2;

            int curAverage = average3(arr, sum, m, s);

            if ((Math.abs(half - curAverage) < Math.abs(half - average)) || ((Math.abs(half - curAverage) == Math.abs(half - average)) && curAverage < average)) {
                average = curAverage;
                ans = m;
            }

            if (curAverage >= half) {
                r = m - 1;
            } else {
                l = m + 1;
            }
        }
        return ans;
    }


    /**
     * 利用前缀和信息, pre数组，可以快速算出一段范围的累加和
     *
     * @param arr
     * @param pre
     * @param k
     * @param s
     * @return
     */
    public static int average3(int[] arr, int[] pre, int k, int s) {
        int n = arr.length;

        if (k < 0) {
            int l = bsZero(arr, k);
            int sum = rangeSum(pre, l + 1, n - 1);
            return (sum + (k * (n - l - 1))) / n;
        } else {
            int r = bsS(arr, k, s);
            int sum = rangeSum(pre, 0, r - 1);
            return (sum + (k * r) + (s * (n - r))) / n;
        }
    }

    private static int bsS(int[] arr, int k, int s) {
        int ans = arr.length;
        int l = 0;
        int r = arr.length - 1;
        int m;
        while (l <= r) {
            m = (l + r) / 2;
            if (arr[m] + k >= s) {
                ans = m;
                r = m - 1;
            } else {
                l = m + 1;
            }
        }
        return ans;
    }

    private static int rangeSum(int[] pre, int l, int r) {
        if (l > r) {
            return 0;
        }
        return l == 0 ? pre[r] : (pre[r] - pre[l - 1]);
    }

    private static int bsZero(int[] arr, int k) {
        int ans = -1;
        int l = 0;
        int r = arr.length - 1;
        int m;

        while (l <= r) {
            m = (l + r) / 2;
            if (arr[m] + k <= 0) {
                ans = m;
                l = m + 1;
            } else {
                r = m - 1;
            }
        }
        return ans;
    }
}
